⟸ Go Back ⟸
Exercise 6 (Homework 3).
(pumping lemma)

Unary sequences with arbitrarily large gaps

Let \boldsymbol a=(a_1,a_2,a_3,\dots) be an ordered sequence of natural numbers. We say that the sequence \boldsymbol a has arbitrarily large gaps if for any n\in \mathbb N there is an index i such that a_{i+1}>a_i +n.

  1. Show that {\boldsymbol a} has arbitrarily large gaps when

    1. a_i=2^i
    2. a_i=i^2
    3. a_i is the i-th Fibonacci number
    4. a_i is the i-th prime number

  2. Given a sequence \boldsymbol a with arbitrarily large gaps, show that the language L_{\boldsymbol a}=\{1^{k} \mid k\in \boldsymbol a\} is not regular.

    Try to prove that L_{\boldsymbol a} is not regular in the following two cases before proving the general result: a_i=2^i and a_i=i^2. This might give you ideas on how to proceed in the general case.

  3. Using the ideas from the previous questions, show that the following languages are not regular:

    1. \{0101^201^3\cdots01^n \mid n\in \mathbb N\}
    2. \{1^n \mid n\text{ is even or prime}\}